#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
int dp[16][1 << 16];
int a[16][16];
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &a[i][j]);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
            dp[0][1 << i] = a[0][i];
        for (int row = 1; row < n; row++)
            for (int i = 0; i < (1 << n); i++)
                for (int j = 0; j < n; j++)
                    if ((i & (1 << j)) && dp[row][i] < dp[row - 1][i - (1 << j)] + a[row][j])
                        dp[row][i] = dp[row - 1][i - (1 << j)] + a[row][j];
        printf("%d\n", dp[n - 1][(1 << n) - 1]);
    }
    return 0;
}
